package org.example.myleet.p787;

import java.util.*;

public class Solution {

    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        //无限距离的一种简单定义
        int INF = Integer.MAX_VALUE;
        //每个节点的花费
        int[] cost = new int[n];
        //点与点之间的航班费用
        int[][] graph = new int[n][n];
        //初始化
        for (int i = 0; i < n; ++i) {
            //初始化时，所有的节点之间通达费用都是无穷
            cost[i] = INF;
            for (int j = 0; j < n; ++j) {
                //初始化时
                if (i == j) {
                    //节点自己本身无需通达费用
                    graph[i][j] = 0;
                } else {
                    //不同的节点之间通达费用都是无穷
                    graph[i][j] = INF;
                }
            }
        }
        //初始化时，起始节点到达的费用为0，因为一开始就在这里
        cost[src] = 0;
        for (int[] flight : flights) {
            //初始化时，将所有航班解析到图中，需要消耗空间复杂度O(n^2)
            graph[flight[0]][flight[1]] = Math.min(graph[flight[0]][flight[1]], flight[2]);
        }
        //BFS专用队列
        Queue<Integer> queue = new LinkedList<>();
        //初始从起始节点开始传播
        queue.offer(src);
        for (int t = 0; t <= k; ++t) {
            //这里是BFS传播和动态规划推导
            int queueSize = queue.size();
            //需要对本回合的费用消耗做一次copy，防止更新最低费用造成的错误
            int[] copyCost = Arrays.copyOf(cost, cost.length);
            //需要对本回合加入到BFS队列中的节点做去重剪枝
            boolean[] inQueue = new boolean[n];
            for (int s = 0; s < queueSize; ++s) {
                //弹出信息传播到达的节点
                int fromCity = queue.poll();
                for (int toCity = 0; toCity < n; ++toCity) {
                    if (toCity != fromCity && graph[fromCity][toCity] < INF) {
                        //首先要保证两个城市之间是有航班的
                        //动态规划推导，取最小的消耗，可能在cost[toCity]、copyCost[toCity]、copyCost[fromCity] + graph[fromCity][toCity]之间
                        cost[toCity] = Math.min(cost[toCity], Math.min(copyCost[toCity], copyCost[fromCity] + graph[fromCity][toCity]));
                        if (!inQueue[toCity]) {
                            //BFS传播
                            queue.offer(toCity);
                            inQueue[toCity] = true;
                        }
                    }
                }
            }
        }
        //如果目的地的费用不是INF表明可以到达，如果是INF就表示不能到达
        return cost[dst] == INF ? -1 : cost[dst];
    }
}
